package com.dushougudu;

import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class LeecodeTree {
    TreeNode root;
    TreeNode node2;
    TreeNode node3;
    TreeNode node4;
    TreeNode node5;
    TreeNode node6;
    TreeNode node7;

    //
//               5
//            /     \
//           4      6
//          / \    / \
//         1   2  7  8
    @Before
    public void init() {
        root = new TreeNode(5);
        node2 = new TreeNode(4);
        node3 = new TreeNode(6);
        node4 = new TreeNode(1);
        node5 = new TreeNode(2);
        node6 = new TreeNode(7);
        node7 = new TreeNode(8);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
    }


    /**
     * 层序遍历
     */
    @Test
    public void levelOrder() {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode treeNode = queue.poll();
                level.add(treeNode.value);
                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                }
            }
            result.add(level);
        }

        for (List<Integer> list : result) {
            for (Integer i : list) {
                System.out.print(i);
            }
            System.out.println();
        }
    }

    /**
     * 二叉树的右视图
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值
     */
    @Test
    public void rightSideView() {
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode treeNode = queue.poll();

                if (i == currentLevelSize - 1) {
                    result.add(treeNode.value);
                }

                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                }
            }
        }

        for (Integer i : result) {
            System.out.println(i);
        }
    }


    /**
     * 翻转二叉树
     */
    @Test
    public void invertTree() {
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode treeNode = queue.poll();

                TreeNode left = treeNode.left;
                TreeNode right = treeNode.right;

                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                }

                treeNode.left = right;
                treeNode.right = left;
            }
        }

        levelOrder();

    }


    /**
     * 对称二叉树
     * 给定一个二叉树，检查它是否是镜像对称的
     */
    @Test
    public void isSymmetric() {
        TreeNode top = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(2);
        TreeNode node7 = new TreeNode(1);

        top.left = node2;
        top.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        System.out.println(checkSymmetric(top, top));
    }

    public boolean checkSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        } else if (left != null && right == null) {
            return false;
        } else if (left == null && right == null) {
            return true;
        } else if (left.value != right.value) {
            return false;
        } else {
            return checkSymmetric(left.left, right.right) && checkSymmetric(left.right, right.left);
        }
    }


    /**
     * 二叉树的最小深度
     */
    @Test
    public void minDepth() {
        TreeNode top = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(2);

        top.left = node2;
        top.right = node3;
        node2.left = node4;
        node2.right = node5;
        System.out.println(getDepth(top));
    }

    public int getDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);

        if (node.left != null && node.right == null) {
            return leftDepth + 1;
        }

        if (node.left == null && node.right != null) {
            return rightDepth + 1;
        }

        return Math.min(leftDepth, rightDepth) + 1;

    }


    /**
     * ⼆叉树，求出该树的节点个数
     */
    @Test
    public void countNodes() {
        int level = 0;
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }

        System.out.println(low);
    }

    public boolean exists(TreeNode root, int level, int k) {
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }


    /**
     * 判断平衡二叉树
     */
    @Test
    public void isBalance() {
        System.out.println(getDepth4Balance(root));
    }

    public int getDepth4Balance(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftDepth = getDepth4Balance(node.left);
        if (leftDepth == -1) {
            return -1;
        }

        int rightDepth = getDepth4Balance(node.right);
        if (rightDepth == -1) {
            return -1;
        }

        return Math.abs(rightDepth - leftDepth) > 1 ? -1 : Math.max(leftDepth, rightDepth) + 1;

    }

}
